package ch2.link.single;

/**
 * 例2.10：有一个长度大于2的整数单链表L，设计一个算法查找L中中间位置的元素。
 * 例如，L=(1，2，3)，返回元素为2；L=(1，2，3，4)，返回元素为2。
 */
public class Exam2_10 {
    public static int Middle1(LinkListClass<Integer> L) {
        int j = 1, n = L.size();
        LinkNode<Integer> p = L.head.next;  // p指向首结点
        while (j <= (n - 1) / 2) {          // 找中间位置的p结点，也可以使用：(int) Math.ceil(n / 2f) - 1)
            j++;
            p = p.next;
        }
        return p.data;
    }

    public static int Middle2(LinkListClass<Integer> linkList) {
        int middle = (int) Math.ceil(linkList.size() / 2.0); // 获取中间位置
        return linkList.GetElem(middle - 1);
    }

    public static int Middle3(LinkListClass<Integer> linkList) {
        int middle = (int) Math.ceil(linkList.size() / 2.0); // 获取中间位置
        LinkNode<Integer> p = linkList.head;
        for (int i = 0; i < middle; i++) {
            p = p.next;
        }
        return p.data;
    }

    public static int Middle4(LinkListClass<Integer> linkList) {
        LinkNode<Integer> slow = linkList.head.next;
        LinkNode<Integer> fast = linkList.head.next;            //均指向首结点
        while (fast.next != null && fast.next.next != null) {   //找中间位置的p结点
            slow = slow.next;                                   //慢指针每次后移1个结点
            fast = fast.next.next;                              //快指针每次后移2个结点
        }
        return slow.data;
    }

    public static void main(String[] args) {
        Integer[] a = {1, 2, 3, 4, 5, 6};
        LinkListClass<Integer> L = new LinkListClass<>();
        L.CreateListR(a);
        System.out.println("L: " + L);
        System.out.println("中间位置的结点值: " + Exam2_10.Middle1(L));
        System.out.println("中间位置的结点值: " + Exam2_10.Middle2(L));
        System.out.println("中间位置的结点值: " + Exam2_10.Middle3(L));
        System.out.println("中间位置的结点值: " + Exam2_10.Middle4(L));
    }
}

